package com.learn.algorithm.dynamic.programming;

public class LeetCode940 {
    public static int distinctSubseqII(String s) {
        int mod = 1000000007;
        int[] cnt = new int[26];
        char[] str = s.toCharArray();
        int all = 1, newAdd;
        for (char x : str) {
            newAdd = (all - cnt[x - 'a'] + mod) % mod;
            cnt[x - 'a'] = (cnt[x - 'a'] + newAdd) % mod;
            all = (all + newAdd) % mod;
        }
        return (all - 1 + mod) % mod;
    }

    public static void main(String[] args) {
        System.out.println(distinctSubseqII("abc"));
        System.out.println(distinctSubseqII("aba"));
        System.out.println(distinctSubseqII("aaa"));
    }
}
